context-free grammar

Terms from Artificial Intelligence: humans at the heart of algorithms

Page numbers are for draft copy at present; they will be replaced with correct numbers when final book is formatted. Chapter numbers are correct and will not change now.

A context-free grammar is described using hierarchical rules. They are used extensively for formal notations such as computer programming languages. They can also be applied to natural language processing, but have limitations The hierarchical rules show how a non-terminal term expands into (or is composed of) some combination of terminals other non-terminals. For example, part of the expansion of a Noun_Phrase (non-terminal) is:
      Noun_Phrase     :=     "the"   Qualified_Noun
On the right 'the' is a terminal, a single word and the end point of grammtical expansion, whereas Qualified_Noun is a non-terminal, which could end up being a single word (e.g. "ball"), but also has expansions including possessives, adjectives, etc. (e.g. "Bella's blue ball"). Note that the rules apply no matter in what context the rule is used, hence 'context free'. However, whether a rule is applied in the first place does depend on previosuly applied grammatical rules. For example one would not attempt to apply the rules for Verb after "the".

Used on Chap. 13: page 302

Also known as context-free